{
 "cells": [
  {
   "cell_type": "markdown",
   "source": [
    "## 支持向量机\n",
    "\n",
    "> reference: 《机器学习实战》第6章 支持向量机\n",
    ">\n",
    "> reference: 《统计学习方法》第7章 支持向量机\n",
    ">\n",
    "> python 3.7"
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "支持向量机是一种二分类模型\n",
    "\n",
    "基本模型是定义在特征空间上的间隔最大的线形分类器。"
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "### 线性可分支持向量机与硬间隔最大化\n",
    "\n",
    "能够将数据集正确划分的平面称作 **分离超平面** 。在训练数据集是线形可分时，则存在着无数个分离超平面，可以将两类数据正确分开。\n",
    "\n",
    "感知机使用误分类数最小的策略求分离超平面，此时可以求得很多的解。\n",
    "\n",
    "线性可分支持向量机利用间隔最大化求解最优分离超平面，此时解唯一。\n"
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "#### 间隔\n",
    "\n",
    "点到分隔面的距离被称作间隔。\n",
    "\n",
    "##### 函数间隔\n",
    "$\\hat{\\gamma_i} = y_i (w\\cdot x_i + b)$\n",
    "\n",
    "超平面关于训练数据集T的函数间隔是超平面关于T中所有样本点的函数间隔最小值：$\\hat{\\gamma} = \\min_{i=1,..,N} \\hat{\\gamma_i}$\n",
    "\n",
    "##### 几何间隔\n",
    "\n",
    "在函数间隔的基础上，施加一个约束，使得$||w||=1$。\n",
    "\n",
    "在样本点$(x_i,y_i)$被超平面$(w,b)$正确分类时，点$x_i$与超平面的距离是\n",
    "$$\\gamma_i = y_i({w\\over ||w|| }\\cdot x_i + {b\\over ||w|| })$$\n",
    "\n",
    "上述定义就是几何间隔。同样定义超平面关于训练数据集的几何间隔\n",
    "${\\gamma} = \\min_{i=1,..,N} {\\gamma_i}$\n",
    "\n",
    "关系：$\\gamma = {\\hat {\\gamma}\\over ||w||}$"
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "#### 间隔最大化\n",
    "\n",
    "间隔最大化的意义是：不仅可以正确分类，而且对最难分的实例点，也有足够大的确信度将其分开。\n",
    "\n",
    "##### 最大间隔分离超平面\n",
    "\n",
    "表示为式子说的约束最优化问题：\n",
    "\n",
    "$$\n",
    " \\max_{w,b} \\gamma\n",
    " \\\\\n",
    " s.t. \\ \\ y_i({w\\over ||w|| }\\cdot x_i + {b\\over ||w|| }) \\ge \\gamma, \\ \\ i=1,2,..,N\n",
    "$$\n",
    "\n",
    "或者转换为函数间隔的形式：\n",
    "\n",
    "$$\n",
    " \\max_{w,b} {\\hat{\\gamma} \\over ||w||}\n",
    " \\\\\n",
    " s.t. \\ \\ y_i({w }\\cdot x_i + {b}) \\ge \\hat{ \\gamma}, \\ \\ i=1,2,..,N\n",
    "$$\n",
    "\n",
    "$\\hat{gamma}$的取值并不影响问题的解，取$\\hat{gamma} = 1$。\n",
    "\n",
    "然后$\\max {1\\over ||w||}$的目标和$\\min {1\\over 2} ||w||^2$的目标等价\n",
    "\n",
    "最后转换就得到了\n",
    "$$\n",
    " \\min_{w,b} {1 \\over 2}||w||^2\n",
    " \\\\\n",
    " s.t. \\ \\ y_i({w}\\cdot x_i + {b}) -1 \\ge 0, \\ \\ i=1,2,..,N\n",
    "$$\n",
    "\n",
    "变成了凸二次规划问题。然后求解该问题的解得到$w^*,b^*$就可以得到最大间隔分离超平面$w^*\\cdot x +b^* = 0$和分类决策函数$f(x) = sign(w^*\\cdot x +b^*)$"
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "#### 另一种描述\n",
    "> 来自《机器学习实战》\n",
    "\n",
    "$$arg \\max_{w,b} \\{ \\min_n (y\\cdot (\\vec{w^T} \\vec{x} +b)) \\cdot {1\\over ||w||}\\}$$"
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "#### 支持向量和间隔边界\n",
    "\n",
    "支持向量是离分离超平面距离最近的实例点。支持向量满足\n",
    "$$\n",
    "    y_i(w\\cdot x_i + b) - 1 = 0\n",
    "$$\n",
    "\n",
    "在决定分离超平面的时候，只有支持向量起作用。若改动间隔边界外的实例点，并不会改变解。\n"
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "outputs": [],
   "source": [],
   "metadata": {
    "collapsed": false
   }
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}
